テンプレート照合装置及びその方法

专利摘要:
テンプレート画像の大きさを変化させて照合しても、高速化できるテンプレート照合装置を提供する。テンプレート照合装置は、テンプレート画像を入力するテンプレート入力部１００と、照合対象となる画像を入力する信号入力部１０１と、テンプレート画像を伸縮するテンプレート伸縮部１０２と、伸縮したテンプレート画像と入力画像とを照合する照合部１０３と、照合によって得られた類似度に基づいてテンプレート画像の伸縮率を決定する限界値算出部１０４と、予め定められた伸縮率の範囲内を全て照合し終えると、照合結果を出力する結果出力部１０５とから構成される。
公开号:JP2011514991A
申请号:JP2009514299
申请日:2009-03-02
公开日:2011-05-12
发明作者:善啓 大盛
申请人:株式会社東芝；
IPC主号:G06T7-00

专利说明:

[0001] 本発明は、テンプレートを拡大、又は、縮小しながら入力信号と高速に照合するテンプレート照合装置及びその方法に関する。]
背景技術

[0002] 非特許文献１が開示するテンプレート画像照合において、予め与えられた閾値θに達しない類似度をもつ領域内で照合を省略することによって高速に探索するアクティブ探索法が提案されている。]
[0003] テンプレート画像を僅かに移動しても類似度が急激に変化しない性質に基づいて、テンプレート画像の周囲における類似度の上限からその領域は導かれる。]
[0004] これにより、アクティブ探索法はテンプレート画像の位置の検出に関して高速化した。]
先行技術

[0005] 村瀬洋、Ｖ．Ｖ．Ｖｉｎｏｄ、「局所色情報を用いた高速物体検索・アクティブ探索法」 信学論（Ｄ−ＩＩ）、ｖｏｌ．Ｊ８１−Ｄ−ＩＩ、ｎｏ．９、ｐｐ．２０３５−２０４２、Ｓｅｐｔ．１９９８．]
発明が解決しようとする課題

[0006] 入力画像中で照合する大きさが不明の場合、テンプレート画像の大きさを少しずつ変化させることによってテンプレートを探索する必要がある。そのため、従来手法は大きさの変化に関して高速化できなかった。]
[0007] そこで、本発明は、テンプレート画像の大きさを変化させて照合しても、高速化できるテンプレート照合装置及びその方法を提供する。]
課題を解決するための手段

[0008] 本発明は、入力信号を入力する入力部と、（１）予め決められた初期値の大きさのテンプレート、又は、前記初期値の大きさのテンプレートを任意の伸縮率で順番に拡大、又は、縮小したテンプレートを前記入力信号上で探索位置を移動させながら類似度を求めるものであり、（２）前記各探索位置において、前記テンプレートの特徴量の分布と前記入力信号における探索窓内の特徴量の分布に基づく類似度を求め、（３）前記類似度の中の最大類似度を求める探索部と、前記最大類似度から、前記テンプレートを拡大、又は、縮小したときの最大類似度が閾値を超えないように、前記テンプレートの前記伸縮率の拡大上限値、又は、縮小下限値を算出する限界値算出部と、前記拡大上限値内、又は、前記縮小下限値内の前記伸縮率によって前記テンプレートを拡大、又は、縮小する伸縮部と、前記テンプレートの大きさが任意の範囲に至るまで、前記テンプレートを前記伸縮部によって拡大、又は、縮小し、前記探索部によって、前記拡大、又は、縮小したテンプレートによって探索を繰り返す繰り返し部と、を有するテンプレート照合装置である。]
[0009] また、本発明は、入力信号を入力する入力部と、（１）予め決められた初期値の大きさのテンプレート、又は、前記初期値の大きさのテンプレートを任意の伸縮範囲内の伸縮率で順番に拡大、又は、縮小したテンプレートを前記入力信号上で探索位置を移動させながら類似度を求めるものであり、（２）前記各探索位置において、前記テンプレートの特徴量の分布と前記入力信号における探索窓内の特徴量の分布に基づく類似度を求め、（３）前記類似度の中の最大類似度を求める第１探索部と、前記最大類似度に基づいて前記テンプレートを拡大、又は、縮小したときの、前記入力信号に対する予測最大類似度を予測する予測部と、前記予測最大類似度から、前記テンプレートを拡大、又は、縮小したときの最大類似度が閾値を超えないように、前記テンプレートの前記伸縮率の上限値と下限値を算出する第１限界値算出部と、前記上限値と前記下限値から決まる伸縮範囲内の前記伸縮率によって前記テンプレートを伸縮する伸縮部と、（１）前記伸縮したテンプレートを前記入力信号上で探索位置を移動させながら類似度を求めるものであり、（２）前記各探索位置において、前記テンプレートの特徴量の分布と前記入力信号における探索窓内の特徴量の分布に基づく類似度を求め、（３）前記類似度の中の最大類似度を求める第２探索部と、前記最大類似度から、前記テンプレートを拡大、又は、縮小したときの最大類似度が前記閾値を超えないように、前記テンプレートの伸縮率の拡大上限値、又は、縮小下限値からなる伸縮範囲を算出する第２限界値算出部と、前記第２限界値算出部によって求められた前記伸縮範囲と、前記第１探索部で探索に用いられた前記テンプレートの大きさを決定した前記伸縮範囲が重なっていない場合には、前記伸縮部で用いられる前記伸縮率を変化させるバックトラック部と、前記第２限界値算出部によって求められた前記伸縮範囲と、前記第１探索部で探索に用いられた前記テンプレートの大きさを決定した前記伸縮範囲が重なった場合には、前記第１探索部からの最大類似度に代えて前記第２探索部からの前記最大類似度を前記予測部で用いるように制御する更新部と、前記テンプレートの大きさが任意の範囲に至るまで、前記テンプレートを前記伸縮部によって拡大、又は、縮小し、前記第１探索部と前記第２探索部によって前記拡大、又は、縮小したテンプレートによって探索を繰り返す繰り返し部と、を有するテンプレート照合装置である。]
発明の効果

[0010] 本発明によれば、探索もれを生じないで、テンプレートの伸縮回数を低減して探索を高速化できる。]
図面の簡単な説明

[0011] 実施例１に係わるテンプレート照合装置の構成を示すブロック図である。
実施例１の動作を示すフローチャートである。
実施例１による画像照合の概要説明図である。
実施例１によるテンプレート拡大時の伸縮率上限の算出方法を説明するための図である。
実施例１によるテンプレート縮小時の伸縮率下限の算出方法を説明するための図である。
実施例１によって伸縮幅を変化させながら照合する様子を説明するための図である。
実施例１の第３の変更例でヒストグラム特徴の分布が急激に変化する場合を説明するための図である。
実施例１の第3の変更例でヒストグラム特徴の分布が急激に変化しない場合を説明するための図である。
実施例２による音声照合の概要説明図である。
実施例２によるテンプレート拡大時の伸縮率上限の算出方法を説明するための図である。
実施例２によるテンプレート縮小時の伸縮率下限の算出方法を説明するための図である。
実施例２によって伸縮幅を変化させながら照合する様子を説明するための図である。
実施例２による音声照合と従来手法との処理速度を比較した実験結果である。
実施例４によるテンプレート伸縮時の伸縮率上限の算出方法を説明するための図である。]
実施例

[0012] 以下、本発明の一実施例のテンプレート照合装置について図面に基づいて説明する。]
[0013] 実施例１では、探索空間が２次元のテンプレート照合装置を説明し、実施例２では、探索空間が１次元のテンプレート照合装置を説明し、実施例３では、探索空間がｎ次元のテンプレート照合装置を説明し、実施例４では、探索空間がｎ次元であって、テンプレートの伸縮率が各次元で異なるテンプレート照合装置を説明し、実施例５では平均輝度値によるノルムによって類似度（距離の逆数）を算出するテンプレート照合装置を説明する。]
[0014] (１ 実施例１）
本発明の実施例１のテンプレート照合装置について図１〜図６に基づいて説明する。] 図１ 図２ 図３ 図４ 図５ 図６
[0015] 本実施例では、２次元探索空間として画像照合を例にとって説明する。そして、テンプレート画像の伸縮率αで拡大、又は、縮小させながら照合する。照合した結果、最も類似度が大きかったテンプレート画像の縮尺率αｍａｘと、その位置（ｘｍａｘ，ｙｍａｘ）を出力する。]
[0016] （１−１）テンプレート照合装置の構成
図１は、テンプレート照合装置を示すブロック図である。] 図１
[0017] テンプレート照合装置は、テンプレート画像を入力するテンプレート入力部１００と、照合対象となる画像を入力する信号入力部１０１と、テンプレート画像を伸縮するテンプレート伸縮部１０２と、伸縮したテンプレート画像と入力画像とを照合する照合部１０３と、照合によって得られた類似度に基づいてテンプレート画像の伸縮率を決定する限界値算出部１０４と、予め定められた伸縮率の範囲内を全て照合し終えると、照合結果を出力する結果出力部１０５とから構成される。]
[0018] テンプレート入力部１００は、テンプレート画像信号を入力してメモリに記憶する。]
[0019] 信号入力部１０１は、テンプレート画像と照合する対象となる画像を入力してメモリに記憶する。]
[0020] テンプレート伸縮部１０２は、後述する限界値算出部１０４が決定する伸縮率に基づいてテンプレート画像を伸縮してメモリに記憶する。]
[0021] 照合部１０３は、テンプレート伸縮部で伸縮されたテンプレート画像と、信号入力部で入力した入力画像とを照合し、類似度が最大になる位置を検出する。]
[0022] 限界値算出部１０４は、照合部１０３で検出された類似度に基づいて、テンプレートを伸縮できる上限又は下限の少なくとも一つを算出する。]
[0023] 結果出力部１０５は、最も類似度が高かった伸縮率と、入力画像中での位置を出力する。]
[0024] なお、このテンプレート照合装置は、例えば、汎用のコンピュータ装置を基本ハードウェアとして用いることでも実現することが可能である。すなわち、テンプレート入力部１００、信号入力部１０１、テンプレート伸縮部１０２、照合部１０３、限界値算出部１０４、及び、結果出力部１０５は、上記のコンピュータ装置に搭載されたプロセッサにプログラムを実行させることにより実現することができる。このとき、テンプレート照合装置は、上記のプログラムをコンピュータ装置に予めインストールすることで実現してもよいし、ＣＤ−ＲＯＭなどの記憶媒体に記憶して、あるいはネットワークを介して上記のプログラムを配布して、このプログラムをコンピュータ装置に適宜インストールすることで実現してもよい。また、Ｂ及びＣは、上記のコンピュータ装置に内蔵あるいは外付けされたメモリ、ハードディスクもしくはＣＤ−Ｒ、ＣＤ−ＲＷ、ＤＶＤ−ＲＡＭ、ＤＶＤ−Ｒなどの記憶媒体などを適宜利用して実現することができる。]
[0025] （１−２）拡大時
テンプレート照合装置の動作を図２、図３に基づいて説明する。図２は、テンプレート照合装置の動作を示すフローチャートである。図３は、画像照合の概要説明図である。] 図２ 図３
[0026] 本実施例では、テンプレートを拡大しながら照合を進めても良いし、縮小しながら照合を進めても良い。以下に、まず、テンプレートの伸縮率を１倍からβｌｉｍ倍（但し、βｌｉｍ＞１である）まで拡大しながら照合する場合を説明する。]
[0027] ステップ２００において、限界値算出部１０４の伸縮率αを１に初期化する。]
[0028] 入力したテンプレートの大きさと現在のテンプレートの大きさの比を表す伸縮幅βを１に初期化する。]
[0029] 結果出力部１０５の最大類似度Ｓｍａｘを０に初期化する。]
[0030] 探索位置（ｘ，ｙ）は探索空間の範囲外の（−１，−１）に初期化される。画像の位置は、原点（０，０）から各画素の縦横方向の最大数までの座標で表される。画像を走査する場合には、原点（０，０）の位置から順番に縦横方向で走査していく。]
[0031] テンプレート画像は予めテンプレート入力部１００で入力してメモリに記憶しておく。]
[0032] 照合する対象である画像も予め信号入力部１０１で入力してメモリに記憶しておく。]
[0033] 閾値θを設定する。本発明では、θより小さい類似度をもつ位置は測定されない。]
[0034] ステップ２０１において、テンプレート伸縮部１０２は、伸縮率αで伸縮したテンプレート画像をメモリに記憶する。]
[0035] ステップ２０２において、照合部１０３は、伸縮されたテンプレートと入力画像を照合して、類似度が最大になる探索位置（ｘ，ｙ）とその類似度Ｓを検出する。]
[0036] 本実施形態において、正規化ヒストグラム交差が類似度として用いられる。その照合方法は、類似度が最大になる入力画像上での位置を検出できる方法ならば何でもよい。例えば、非特許文献１の村瀬等による方法や、全ての探索点を全て探索する方法で検出する。]
[0037] 正規化ヒストグラム交差は式１で求める。ｈｗ、ｈｔは、それぞれ入力画像上の探索窓とテンプレートの分布であるヒストグラムを表すｍ次元のベクトル、ｈｗｉ、ｈｔｉはそれぞれ入力画像上の探索窓とテンプレートのｉ番目のヒストグラム要素を表す。]
[0038] ステップ２０３において、結果出力部１０５は、伸縮率αと、類似度が最大になる位置（ｘ，ｙ）とその類似度Ｓを入力する。Ｓｍａｘ＞Ｓの場合には、Ｓｍａｘ＝Ｓに更新する。]
[0039] ステップ２０４において、限界値算出部１０４は、照合で検出された類似度の最大値Ｓと閾値θに基づいて、伸縮率の上限値αｕｐｐｅｒを算出する。αｕｐｐｅｒの算出方法は後述する。伸縮率αは上限値αｕｐｐｅｒを超えない範囲に設定する。αｕｐｐｅｒが予め決められた伸縮率の最小値αｍｉｎを下回る場合には、α＝αｍｉｎとする。]
[0040] ステップ２０５において、伸縮幅をβ＝β×αで更新する。]
[0041] ステップ２０６において、伸縮幅がβ≧βｌｉｍならばステップ２０１に戻り、ステップ２０１からステップ２０５までの処理を繰り返す。β＞βｌｉｍならばステップ２
ステップ２０７において、結果出力部１０５は、最大類似度Ｓｍａｘとその探索位置（ｘ，ｙ）を出力し、処理を終了する。]
[0042] （１−３）拡大時の伸縮率上限の算出方法
次に、テンプレート拡大時の伸縮率上限の算出方法について図４、図６に基づいて説明する。] 図４ 図６
[0043] 図４は、テンプレート拡大時の伸縮率上限の算出方法を説明するための図である。] 図４
[0044] 図４の上部が元の大きさのテンプレート画像と入力画像を照合する様子であり、図４の下部が拡大されたテンプレート画像と入力画像を照合する様子を示す。図６は、伸縮幅βを変化させながら照合する様子を説明するための図である。] 図４ 図６
[0045] Ｓは、元の大きさのテンプレートでの類似度である。但し、０≦Ｓ≦１である。]
[0046] Ｓｂ１は、拡大後における元のテンプレートの範囲内での最大類似度である。但し、０≦Ｓｂ１≦１である。]
[0047] Ｓｂ２は、拡大後におけるテンプレートのはみ出しによる最大類似度である。但し、０≦Ｓｂ２≦１である。]
[0048] αは、テンプレートの一辺の伸縮率（拡大率）である。但し、１＜αである。]
[0049] Ｒ１は、元のテンプレートでの照合範囲である探索窓である。]
[0050] Ｒ２は、拡大したテンプレートでの探索窓である。]
[0051] このようにテンプレートをα倍にして照合すると、図４中左下の網掛け領域に示すように、拡大されたテンプレート上での一致画素数はα２倍に増える。] 図４
[0052] 正規化ヒストグラム交差で類似度を算出する際に、入力画像上で一致する可能性のある画素が十分多いと仮定すると、図４中右下の斜線領域に示すように、元のテンプレートでの探索窓Ｒ１における拡大後の類似度上限はＳｂ１＝Ｓとなる。] 図４
[0053] 一方、拡大したテンプレートでの探索窓Ｒ２のうち、Ｒ１をはみ出した領域は全て類似度の増加に寄与すると仮定すると、 はみ出しによる最大類似度はＳｂ２＝１−１／α２となる。したがって、拡大後の類似度上限は以下の式２で表せる。]
[0054] Ｓｂ＝Ｓｂ１＋Ｓｂ２＝Ｓ＋１−１／α２ ・・・（２）

Ｓｂ＜θをα２について解くと、

−１／α２＜θ−１−Ｓ

となる。θは予め与えられた閾値とする。但し、０≦θ≦１である。そして、常にθ−１−Ｓ＜０であるため、

α２＜１／（１＋Ｓ−θ）

となる。いまは拡大について考えているため、α２＞１、すなわち、Ｓ＜θでなければならない。]
[0055] したがって、Ｓｂ＜θを満たすα２の範囲は以下の式３で表せる。]
[0056] １＜α２＜１／（１＋Ｓ−θ）、但し、Ｓ＞θである。 ・・・（３）

（１−４）縮小時
上記ではテンプレートを拡大する場合について説明したが、テンプレートを縮小しても同様に高速化できる。この場合はステップ２０４とステップ２０６のみが異なる。以下に、テンプレートを１倍からαｌｏｗｅｒ倍まで縮小しながら照合する場合について、その差分のみをステップ２０４’、ステップ２０６’として説明する。]
[0057] ステップ２０４’において、限界値算出部１０４は、照合で検出された類似度の最大値Ｓに基づいて、伸縮率の下限値αｌｏｗｅｒを算出する。αｌｏｗｅｒの算出方法は後述する。伸縮率αは下限値αｌｏｗｅｒを下回らない範囲に設定する。αｕｐｐｅｒが予め決められた伸縮率の最小値αｍｉｎを下回る場合には、α＝αｍｉｎとする。]
[0058] ステップ２０６’において、伸縮幅がβ≧βｌｉｍならばステップ２０１に戻り、ステップ２０１からステップ２０５までの処理を繰り返す。そうでなければステップ２０７に進む。]
[0059] （１−５）縮小時の伸縮率下限の算出方法
次に、テンプレート縮小時の伸縮率下限の算出方法について図５に基づいて説明する。] 図５
[0060] 図５は、テンプレート縮小時の伸縮率下限の算出方法を説明するための図である。図５の上部が元の大きさのテンプレート画像と入力画像を照合する様子であり、図５の下部が縮小されたテンプレート画像と入力画像を照合する様子を示す。] 図５
[0061] Ｓは、元の大きさのテンプレートでの類似度である。但し、０≦Ｓ≦１である。]
[0062] Ｓｃは、縮小後における元のテンプレートの範囲内での最大類似度である。但し、０≦Ｓｂ１≦１である。]
[0063] αは、テンプレートの一辺の伸縮率である。但し、０＜α＜１である。]
[0064] Ｒ１は、元のテンプレートでの探索窓である。]
[0065] Ｒ３は、縮小したテンプレートでの探索窓である。]
[0066] 図５中右下の網掛け領域に示すように、入力画像上での一致画素数は不変である。] 図５
[0067] そして、図５中左下の斜線領域に示すように、正規化ヒストグラム交差で類似度を算出する際に、テンプレート上で一致する可能性のある画素が十分多いと仮定すると、テンプレート縮小後の入力画像上での探索窓Ｒ２における類似度上限Ｓｃ＝Ｓ／α２（但し、α＜１である）となる。] 図５
[0068] 縮小では拡大のようなはみ出し領域は生じない。したがって、縮小後の類似度上限は以下の式４で表せる。]
[0069] Ｓｃ＝Ｓ／α２ ・・・（４）

Ｓｃ＜θを満たすα２の範囲を求めると以下の式５となる。]
[0070] Ｓ／θ＜α２＜１ ・・・（５）

（１−６）伸縮率
式３と式５をまとめてα＝１の場合も含めると、α２の上限と下限は以下の式６で表せる。]
[0071] Ｓ／θ＜α２＜１／（１＋Ｓ−θ） ・・・（６）

（１−７）効果
このように実施例１によれば、類似度が予め与えられた閾値θを下回るテンプレートの大きさでの照合を省略することで高速化ができる。]
[0072] （１−８ 変更例１）
変更例１では、正規化ヒストグラム交差で類似度を算出する際に、一致する画素数に制限がある場合を説明する。すなわち、実施例１では、拡大したテンプレートと探索窓で一致する可能性のある画素数が十分に多いと仮定した。しかし、限りがある場合には、テンプレートの拡大による類似度増加は、実施例１の場合以下となり、よりテンプレートを大きくしないと類似度が閾値θを超えない。この性質を利用すると、伸縮率αの上限と下限をさらに広げることができる。]
[0073] （１−８−１）伸縮率の上限の算出方法
まず、正規化ヒストグラム交差で類似度を算出する際に、拡大したテンプレートと探索窓で一致する可能性のある画素数に限りがある場合について、伸縮率αの上限の算出方法を説明する。]
[0074] 拡大後の類似度Ｓｂ１を可能性のある最大値としないで、実際に算出する。本変更例では類似度を正規化ヒストグラム交差で算出するため、ヒストグラムのビン毎に上限を算出すると、式１を用いて、拡大後の類似度上限Ｓｂ（α２）は以下の式７で表せる。]
[0075] Ｓｂ（α２）＝Ｓ（ｈｗ、α２ｈｔ）＋１−１／α２ ・・・（７）

Ｓｂ（α２）＜θを満たすα２の範囲を求めることを考える。式７の右辺第一項Ｓ（ｈｗ、α２ｈｔ）と第三項−１／α２は、α２について単調増加するため、Ｓｂ（α２）はα２について単調増加する。よってα２の上限値は、Ｓｂ（α２）＝θの解として求まる。例えば、方程式を満たすまでα２を微小に増加させながら方程式を満たすかどうかを調べる山登り法によって求まる。厳密解が得られない場合は、厳密解の近傍でＳｂ（α２）＜θを満たす近似解を求めれば良い。]
[0076] したがって、Ｓｂ（α２）＜θを満たすα２の範囲は以下の式８で表される。但し、ｆ−１（θ）は関数ｆ（α）＝θとなるαの値を表す。]
[0077] （１−８−２）伸縮率の下限の算出方法
縮小時にも、正規化ヒストグラム交差で類似度を算出する際に、拡大したテンプレートと探索窓で一致する可能性のある画素数に限りがある場合には、伸縮率αの下限をさらに小さくできる。以下にその下限の算出方法を説明する。]
[0078] 縮小後の類似度Ｓｃを可能性のある最大値としないで、実際に算出する。本変更例では類似度を正規化ヒストグラム交差で算出するため、ヒストグラムのビン毎に下限を算出すると、縮小後の類似度Ｓｃ（α２）は以下の式９で表せる。]
[0079] Ｓｃ（α２）＜θを満たすα２の範囲を求めることを考える。式１３の右辺はα２について単調減少するため、Ｓｃ（α２）はα２について単調増加する、よってα２の下限値は、Ｓｃ（α２）＝θの解として求まる。]
[0080] したがって、Ｓｃ（α２）＜θを満たすα２の範囲は以下の式１０で表せる。]
[0081] （１−８−３）まとめ
式８と式１０をまとめると、伸縮率α２の上限と下限は以下の式１１で表せる。]
[0082] （１−８−４）効果
本変更例では、伸縮率αの上限と下限を算出する処理量は増加する。しかし、通常の画像照合では、伸縮率αの上限と下限を拡大できることによる処理の削減量と比較すると非常に小さい。よって、本変更例によって、さらに高速化ができる。]
[0083] （１−９ 変更例２）
変更例２では、上限と下限の両方を利用する場合について説明する。すなわち、実施例１では、テンプレート画像を縮小させるのに、伸縮率の下限又は上限のうち一つのみを用いたが、これに限らず、伸縮率の上限と下限の両方を用いてもよい。]
[0084] この場合は、日本の特許第３４７４１３１号公報の探索窓の位置を伸縮率αに、類似度をステップ２０２で検出する類似度Ｓに置き換えて考える。テンプレートを拡大させながら照合する場合を以下に説明する。]
[0085] まず、テンプレート照合を行い、最大類似度Ｓを求める。伸縮率αの周辺の伸縮率でも最大類似度Ｓ’は急激に変化しないと仮定して、Ｓ’＝Ｓと予測する。式６を用いて伸縮率の下限を求めると、√（Ｓ／θ）となる。テンプレートをα’倍した場合に算出した伸縮率の下限がαを含んで、伸縮幅が連続するようにα’を予測する。そのようなα’はいくつも存在するが、最もαから離れた位置からγ戻ったα’＝√（Ｓ／θ）−γを伸縮度決定部１０４で決定する。但し、γは固定値とする。ここで連続とは、前回の伸縮率の上限と下限から決まる伸縮範囲と、今回の伸縮率の上限と下限から決まる伸縮範囲とが重なった状態をいう。もし、重なっていなければ、前回の伸縮範囲と、今回の伸縮範囲との間に隙間（探索しない伸縮率）ができて不連続となるからである。]
[0086] 実際にテンプレートをα’倍に拡大して、実際の類似度Ｓ"を算出し、実際の伸縮率の上限値αｕｐｐｅｒ’と下限値αｌｏｗｅｒ’を算出する。下限値はαｌｏｗｅｒ’＝√（Ｓ”／θ）なので、√（Ｓ／θ）≦√（Ｓ”／θ）−γの場合は伸縮率が連続し、そうでない場合は不連続であると判定する。]
[0087] 予測に失敗して伸縮率の範囲にαが含まれなかった場合、すなわち、伸縮率の上限値αｕｐｐｅｒ’から下限値αｌｏｗｅｒ’までの範囲と前回の伸縮率の上限値αｕｐｐｅｒから下限値αｌｏｗｅｒまでの範囲とが重ならならず不連続となった場合には、伸縮率α’をαに近付けて、再度照合を試みるバックトラック処理を行う。伸縮率α’をαに近付ける方法は何でも良く、伸縮率αに近づく方向に伸縮率α’を固定幅や固定倍率増減させても良いし、α’とαの２値の平均値を新たなα’としても良い。]
[0088] 予測に成功した場合は、新たな最大類似度をαｍａｘとし、全ての伸縮範囲を探索するまで上記の処理を繰り返す。]
[0089] 本変更例によれば、実施例１と比較して伸縮率の変化幅を大きくでき、さらに高速化できる。テンプレートを縮小しながら照合する場合も上記と同様に高速化できる。]
[0090] （１−１０ 変更例３）
変更例３では、テンプレートの拡大・縮小方法の具体例を図７と図８に基づいて説明する。すなわち、実施例１におけるテンプレートの伸縮方法は、伸縮前と伸縮後でヒストグラム特徴の分布が急激に変化しない方法が望ましい。] 図７ 図８
[0091] ４×４のテンプレート画像を２×２に縮小する場合を例にとって説明する。縮小前のテンプレートの各要素を、Ｐ１（ｘ，ｙ）、縮小後の要素をＰ２（ｘ，ｙ）で表す。但しｘは行、ｙは列を表す。]
[0092] （１−１０−１）問題点
図７は、テンプレート画像を４分割して、それぞれの領域の輝度値を平均する場合を示す。輝度値の最大値を８とし、縮小前には輝度値が０と８の２種類しかないとする。図７の下図は、輝度値に対する出現頻度を表す。縮小前には、輝度値が０と８の画素が同数ある。] 図７
[0093] 平均によって画像を縮小すると、

Ｐ２（１，１）＝（８＋０＋８＋０）／４＝４、

Ｐ２（１，２）＝４、

Ｐ２（２，１）＝（０＋０＋８＋０）／４＝２、

Ｐ２（２，２）＝（８＋８＋０＋８）／４＝６

となる。]
[0094] よって、図７の下図の分布図に示すように、輝度値の頻度分布が大きく変わって、縮小前とは異なる輝度値が出現してしまう。実施例１では、類似度を正規化ヒストグラム交差で算出するため、輝度値のヒストグラム特徴の分布が大きく変化すると、類似度が意味をなさなくなる可能性があるという問題点がある。] 図７
[0095] （１−１０−２）解決方法
図８は、テンプレート画像を４分割して、それぞれの領域から代表する画素をランダムに選択する場合を示す。この場合は、縮小前とは異なる輝度値が出現せず、輝度値のヒストグラム特徴の分布が大きく変わらないため、正規化ヒストグラム交差を算出できる。] 図８
[0096] （１−１１ 変更例４）
変更例４では、入力画像を分割する場合を説明する。すなわち、実施例１では、ステップ２０２において入力画像全体でテンプレート照合した。ステップ２０２では入力画像の類似度の最大値Ｓを算出するため、入力画像のほとんどが類似度０であっても一点だけ類似度が大きい場合には、テンプレートの伸縮率を大きく変化できない。]
[0097] そこで、入力画像を複数の領域に分割して、各領域に独立してテンプレート照合しても良い。例えば、入力画像を４分割して、それぞれの領域を独立した画像とみなしてテンプレート照合する。]
[0098] これにより、テンプレートと類似する部分が少ししか含まれない入力画像も、テンプレートと類似する部分を含む領域のみを詳細に探索して、その他の領域は伸縮率の変化を大きくして高速に探索できる。]
[0099] また、入力画像の各画素を分割領域とみなしても良い。テンプレートを拡大しながら照合する場合は、まず、入力画像の各画素について、伸縮率の上限値を記憶する。上限値の最小値を次のテンプレートの伸縮率として変化させた場合に、各画素に記憶された上限値の範囲内ならば類似度の算出を省略する。]
[0100] （２ 実施例２）
本発明の実施例２のテンプレート照合装置について図９〜図１３に基づいて説明する。] 図１０ 図１１ 図１２ 図１３ 図９
[0101] 本実施例では、１次元探索空間の場合について説明する。すなわち、実施例１では探索空間が２次元である画像照合を例にとって説明したが、本実施例では、テンプレート照合装置を１次元の探索空間に適用する。具体的には、音声照合を例にとって説明する。音声照合において伸縮とは、音声信号を時間方向に伸縮することをいう。]
[0102] 本実施例に係わる音声のテンプレート照合装置における構成と処理手順は、実施例１に係わる画像のテンプレート照合装置と同一であり、限界値算出部１０４での伸縮率の算出方法のみが異なる。以下にその方法を説明する。]
[0103] （２−１）拡大時
まず、テンプレートを１倍からαｕｐｐｅｒ倍（但し、αｕｐｐｅｒ＞１である）まで拡大しながら照合する場合を説明する。]
[0104] 図９は、音声照合の概要説明図である。画像照合の場合と同様に、図９中右側のテンプレートを伸縮させながら、図９中左側の入力音声と照合する。] 図９
[0105] 図１０は、テンプレート拡大時の伸縮率上限の算出方法を説明するための図である。] 図１０
[0106] 図１０の上部が、元の大きさのテンプレート音声と入力音声を照合する様子であり、図１０の下部が、拡大されたテンプレート音声と入力音声を照合する様子を示す。] 図１０
[0107] Ｓは、元の大きさのテンプレートでの類似度である。但し、０≦Ｓ≦１である。]
[0108] Ｓｂ１は、拡大後における元のテンプレートの範囲内での類似度の上限値である。但し、０≦Ｓｂ１≦１である。]
[0109] Ｓｂ２は、拡大後におけるテンプレートのはみ出しによる類似度の上限値である。但し、０≦Ｓｂ２≦１である
αは、テンプレートの一辺の伸縮率である。但し、１＜αであう。]
[0110] そして、図１０中左下の網掛け領域に示すように、拡大されたテンプレート上での一致画素数はα倍に増える。図１０中右下の斜線領域に示しように、正規化ヒストグラム交差で類似度を算出する際に、入力画像上で一致する可能性のある画素が十分多いと仮定すると、元のテンプレートでの拡大後の類似度上限Ｓｂ１＝Ｓとなる。] 図１０
[0111] 一方、拡大したテンプレートでのＲ１をはみ出した領域は全て類似度増加に寄与し得る。よって、はみ出しによる最大類似度はＳｂ２＝１−１／αとなる。したがって、拡大後の類似度上限は以下の式１２で表せる。]
[0112] Ｓｂ＝Ｓｂ１＋Ｓｂ２＝１＋Ｓ−１／α ・・・（１２）

Ｓｂ＜θを満たすαの範囲を求めると以下の式１３で表せる。]
[0113] １＜α＜１／（１＋Ｓ−θ）、但し、Ｓ＞θである。 ・・・（１３）

（２−２）縮小時
次に、テンプレートを１倍からαｌｏｗｅｒ倍（但し、αｌｏｗｅｒ＜１である）まで縮小しながら照合する場合を図１１に基づいて説明する。] 図１１
[0114] 図１１中右下の網掛け領域に示すように、入力音声上での一致サンプル数は不変である。図１１中左下の斜線領域に示すように、正規化ヒストグラム交差で類似度を算出する際に、テンプレート上で一致する可能性のあるサンプルが十分多いと仮定すると、テンプレート縮小後の入力音声上での類似度上限Ｓｃ＝Ｓ／α（但し、α＜１である）となる。] 図１１
[0115] 縮小では拡大のようなはみ出し領域は生じない。したがって、縮小後の類似度上限は以下の式１４で表せる。]
[0116] Ｓｃ＝Ｓ／α ・・・（１４）

Ｓｃ＜θを満たすαの範囲を求めると以下の式１５となる。]
[0117] Ｓ／θ＜α＜１ ・・・（１５）

（２−３）まとめ
式１３と式１５をまとめると、伸縮率αの上限と下限は以下の式１６で表せる。]
[0118] Ｓ／θ＜α＜１／（１＋Ｓ−θ） ・・・（１６）

（２−４）効果
このように本実施例によれば、音声信号を照合する場合には、画像照合のα２をαに置き換えた式１６で、伸縮度の上限と下限が求まる。]
[0119] 図１３に音声照合において、実施例２による処理時間と従来手法の処理時間を比較した結果を示す。図１３に示すように２０倍以上高速化できた。] 図１３
[0120] （２−５）変更例
実施例１の第１の変更例と同様に、拡大したテンプレートと探索窓で一致する可能性のある画素数に限りがある場合には、式１５のα２をαに置き換えた以下の式１７で表せる。]
[0121] （３ 実施例３）
本発明の実施例３のテンプレート照合装置について説明する。]
[0122] 本実施例では、ｎ次元探索空間の場合について説明する。すなわち、実施例１では探索空間が２次元である画像照合を例にとって説明し、実施例２では探索空間が１次元である音声照合を例にとって説明した。本実施例では、ｎ次元の探索空間での信号照合に拡張した場合について説明する。]
[0123] 伸縮時に正規化ヒストグラム交差で類似度を算出する際に、一致する可能性のある信号が十分にある場合には、伸縮率αｎの上限と下限は以下の式１８で表せる。]
[0124] Ｓ／θ＜αｎ＜１／（１＋Ｓ−θ） ・・・（１８）

実施例１の第１の変更例と同様に、正規化ヒストグラム交差で類似度を算出する際に、拡大したテンプレートと探索窓で一致する可能性のある画素数に限りがある場合には、伸縮時に一致する信号に限りがあることを考慮する場合には、伸縮率αｎの上限と下限は以下の式１９で表せる。]
[0125] （４ 実施例４）
本発明の実施例４のテンプレート照合装置について図１４に基づいて説明する。] 図１４
[0126] 本実施例では、伸縮率が各次元で独立の場合について説明する。すなわち、探索空間が２次元以上のこれまでの各実施例では、各次元の伸縮率は等倍率としたが、本実施例では、各次元の伸縮率が異なる場合について説明する。]
[0127] （４−１）２次元の場合
図１４を用いて、２次元の探索空間である画像探索の場合のテンプレート伸縮時の伸縮率上限の算出方法を説明する。図１４は図４とほとんど同じであるが、テンプレートの伸縮率が縦α１、横α２で均一でない点が異なる。] 図１４ 図４
[0128] 図１４中左下の網掛け領域に示すように、拡大されたテンプレート上での一致画素数はα１×α２倍に増える。図１４中右下の斜線部分に示すように、正規化ヒストグラム交差で類似度を算出する際に、入力画像上で一致する可能性のある画素が十分に多いと仮定すると、元のテンプレートでの探索窓Ｒ１における拡
大後の類似度上限はＳｂ１＝Ｓとなる。] 図１４
[0129] 一方、拡大したテンプレートでの探索窓Ｒ２のうち、Ｒ１をはみ出した領域は全て類似度増加に寄与し得る。よって、この図１４のようにα１＞１、α２＜１の場合には、はみ出しによる最大類似度は、

Ｓｂ２＝１−１／α１×１

となる。辺が縮小する場合にははみ出しがなくなることを考慮して一般的に表すと、

Ｓｂ２＝１−ｍｉｎ（１，１／α１）×ｍｉｎ（１，１／α２）

と表せる。したがって、拡大後の類似度上限は以下の式２０で表せる。但し、関数ｍｉｎ（・）は２つの変数の最小値を出力する関数とする。] 図１４
[0130] Ｓｂ＝Ｓｂ１＋Ｓｂ２＝Ｓ＋１−ｍｉｎ（１，１／α１）×（１，１／α２）

・・・（２０）

（４−２）ｎ次元の場合
次に、より一般的なｎ次元の場合について説明する。]
[0131] 図１のように入力信号に一致する信号が十分にある場合には、

Ｓｂ１＝Ｓ、

Ｓｂ２＝１−ｍｉｎ（１，１／α１）×ｍｉｎ（１，１／α２）×・・・×ｍｉｎ（１，１／αｎ）

となる。この場合は伸縮率の上限を与える。] 図１
[0132] 図５のように、正規化ヒストグラム交差で類似度を算出する際に、テンプレートに一致する信号が十分にある場合には、

Ｓｂ１＝Ｓ／（ｍｉｎ（１，１／α１）×ｍｉｎ（１，１／α２）×・・・×ｍｉｎ（１，１／αｎ））、

Ｓｂ２＝１−ｍｉｎ（１，１／α１）×ｍｉｎ（１，１／α２）×・・・×ｍｉｎ（１，１／αｎ）

となる。この場合は伸縮率の下限を与える。] 図５
[0133] したがって、ｎ次元の伸縮率ベクトルαの上限と下限は以下の式２１で表せる。]
[0134] （４−３）変更例
実施例１の第１の変更例と同様に、正規化ヒストグラム交差で類似度を算出する際に、拡大したテンプレートと探索窓で一致する可能性のある画素数に限りがある場合には、伸縮率ベクトルαの上限と下限は以下の式２２で表せる。但し、Ｉは単位ベクトルを表す。]
[0135] （５ 実施例５）
実施例５では、実施例１で用いる類似度として、輝度平均値のノルムによって算出する距離を用い
る場合を説明する。すなわち、これまでの実施例では、ステップ２０３において、テンプレート画像の特徴量のヒストグラムと、入力画像の特徴量のヒストグラムの間で正規化ヒストグラム交差を算出したが、テンプレート画像の伸縮によって類似度の上限が求まる方法であれば、類似度の算出方法は何でも良い。]
[0136] ここではその一例として、平均輝度のＬ１ノルム、すなわち差分の絶対値を用いる場合を説明する。但し、類似度の代わりに距離を用いる場合は、数値の大小の意味が反転するから、類似度の上限を求めることに注意が必要である。]
[0137] （５−１）拡大時の伸縮率上限の算出方法
まず、テンプレート画像を拡大する場合を説明する。テンプレート画像及び入力画像の平均輝度値をそれぞれｃ１、ｃ２、閾値をθとすると、距離はＤ＝｜ｃ１−ｃ２｜で求まる。但し、｜・｜は絶対値を出力するものとする。ｃ２−ｃ１＞θの場合とｃ１−ｃ２＞θの場合に分けて説明する。]
[0138] （５−１−１）拡大時にｃ２−ｃ１＞θの場合
テンプレート画像の平均輝度ｃ２よりも入力画像の平均輝度ｃ１の方が大きい場合であり、入力画像上に設定した探索窓の拡大後の平均輝度ｃ２’を減少させることを考える。拡大によってはみ出した領域全てが平均輝度ｃ２’の減少に寄与すると仮定すると、ｃ２’＝ｃ２／α２となる。よって拡大後の距離Ｄｂ＝ｃ２’−ｃ１はＤｂ＝ｃ２／α２—ｃ１となる。Ｄｂ＞θをα２について解くと、

α２＜ｃ２／（ｃ１＋θ） ・・・（２３）

となる。]
[0139] （５−１−２）拡大時にｃ１−ｃ２＞θの場合
テンプレート画像の平均輝度ｃ２よりも入力画像の平均輝度ｃ１の方が小さい場合であり、入力画像上に設定した探索窓の拡大後の平均輝度ｃ２’を増加させることを考える。拡大によってはみ出した領域全てが平均輝度ｃ２’の増加に寄与すると仮定すると、ｃ２’＝（ｃ２＋α２−１）／α２となる。よって拡大後の距離Ｄｂ＝ｃ１−ｃ２’はＤｂ＝ｃ１−（ｃ２＋α２−１）／α２となる。Ｄｂ＞θをα２について解くと、

α２＜（１−ｃ２）／（１−ｃ１＋θ） ・・・（２４）

となる。]
[0140] （５−２）縮小時の伸縮率上限の算出方法
縮小時もｃ２−ｃ１＞θの場合とｃ１−ｃ２＞θの場合に分けて説明する。]
[0141] （５−２−１）縮小時にｃ２−ｃ１＞θの場合
テンプレート画像の平均輝度ｃ２よりも入力画像の平均輝度ｃ１の方が大きい場合であり、入力画像上に設定した探索窓の縮小後の平均輝度ｃ２’を減少させることを考える。縮小によって探索窓の範囲外となる領域全てが平均輝度ｃ２’の減少に寄与すると仮定すると、ｃ２’＝（ｃ１＋α２−１）／α２となる。よって縮小後の距離Ｄｃ＝ｃ２’−ｃ１はＤｃ＝（ｃ１＋α２−１）／α２−ｃ１となる。Ｄｃ＞θをα２について解くと、

α２＞（１−ｃ２）／（１−ｃ１−θ） ・・・（２５）

となる。]
[0142] （５−２−２）縮小時にｃ１−ｃ２＞θの場合
テンプレート画像の平均輝度ｃ２よりも入力画像の平均輝度ｃ１の方が小さい場合であり、入力画像上に設定した探索窓の縮小後の平均輝度ｃ２’を増加させることを考える。縮小によって探索窓の範囲外となる領域全てが平均輝度ｃ２’の増加に寄与すると仮定すると、ｃ２’＝ｃ２／α２となる。よって縮小後の距離Ｄｃ＝ｃ１−ｃ２’は、ｃ１−ｃ２／α２となる。Ｄｃ＞θをα２について解くと、

α２＞ｃ２／（ｃ１−θ） ・・・（２６）

となる。]
[0143] （５−３）まとめ
式２３と式２４をまとめると、ｃ２−ｃ１＞θの場合は

（１−ｃ２）／（１−ｃ１−θ）＜α２＜ｃ２／（ｃ１＋θ） ・・・（２７）

となる。]
[0144] 式２４と式２６をまとめると、ｃ１−ｃ２＞θの場合は

ｃ２／（ｃ１−θ）＜α２＜（１−ｃ２）／（１−ｃ１＋θ） ・・・（２８）

となる。]
[0145] （５−４）変更例
実施例５では距離の算出方法としてＬ１ノルムを用いたが、差の２乗和であるＬ２ノルム、差のｎ乗和であるＬｎノルムを用いても良い。]
[0146] また、実施例５では探索空間が２次元である画像照合を例にとって説明したが、探索空間が１次元である音声照合や、探索空間がｎ次元でも良い。その場合は式２７及び式２８におけるα２が、１次元の場合はα、ｎ次元の場合はαｎとなる。]
[0147] あるいは、ノルムによって距離を算出しなくても、距離の下限が求まる方法であれば距離の算出方法は何でも良い。類似度の場合は類似度の上限が求まる方法であれば何でも良い。]
[0148] （６ 変更例）
本発明は上記各実施例そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。]
[0149] また、上記実施例に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施例に示される全構成要素から幾つかの構成要素を削除してもよい。]
[0150] さらに、異なる実施例にわたる構成要素を適宜組み合わせてもよい。]

权利要求:

請求項1
入力信号が入力する入力部と、（１）予め決められた初期値の大きさのテンプレート、又は、前記初期値の大きさのテンプレートを任意の伸縮率で順番に拡大、又は、縮小したテンプレートを前記入力信号上で探索位置を移動させながら類似度を求めるものであり、（２）前記各探索位置において、前記テンプレートの特徴量の分布と前記入力信号における探索窓内の特徴量の分布に基づく類似度を求め、（３）前記類似度の中の最大類似度を求める探索部と、前記最大類似度から、前記テンプレートを拡大、又は、縮小したときの最大類似度が閾値を超えないように、前記テンプレートの前記伸縮率の拡大上限値、又は、縮小下限値を算出する限界値算出部と、前記拡大上限値内、又は、前記縮小下限値内の前記伸縮率によって前記テンプレートを拡大、又は、縮小する伸縮部と、前記テンプレートの大きさが任意の範囲に至るまで、前記テンプレートを前記伸縮部によって拡大、又は、縮小し、前記探索部によって、前記拡大、又は、縮小したテンプレートによって探索を繰り返す繰り返し部と、を有するテンプレート照合装置。
請求項2
入力信号が入力する入力部と、（１）予め決められた初期値の大きさのテンプレート、又は、前記初期値の大きさのテンプレートを任意の伸縮範囲内の伸縮率で順番に拡大、又は、縮小したテンプレートを前記入力信号上で探索位置を移動させながら類似度を求めるものであり、（２）前記各探索位置において、前記テンプレートの特徴量の分布と前記入力信号における探索窓内の特徴量の分布に基づく類似度を求め、（３）前記類似度の中の最大類似度を求める第１探索部と、前記最大類似度に基づいて前記テンプレートを拡大、又は、縮小したときの、前記入力信号に対する予測最大類似度を予測する予測部と、前記予測最大類似度から、前記テンプレートを拡大、又は、縮小したときの最大類似度が閾値を超えないように、前記テンプレートの前記伸縮率の上限値と下限値を算出する第１限界値算出部と、前記上限値と前記下限値から決まる伸縮範囲内の前記伸縮率によって前記テンプレートを伸縮する伸縮部と、（１）前記伸縮したテンプレートを前記入力信号上で探索位置を移動させながら類似度を求めるものであり、（２）前記各探索位置において、前記テンプレートの特徴量の分布と前記入力信号における探索窓内の特徴量の分布に基づく類似度を求め、（３）前記類似度の中の最大類似度を求める第２探索部と、前記最大類似度から、前記テンプレートを拡大、又は、縮小したときの最大類似度が前記閾値を超えないように、前記テンプレートの伸縮率の拡大上限値、又は、縮小下限値からなる伸縮範囲を算出する第２限界値算出部と、前記第２限界値算出部によって求められた前記伸縮範囲と、前記第１探索部で探索に用いられた前記テンプレートの大きさを決定した前記伸縮範囲が重なっていない場合には、前記伸縮部で用いられる前記伸縮率を変化させるバックトラック部と、前記第２限界値算出部によって求められた前記伸縮範囲と、前記第１探索部で探索に用いられた前記テンプレートの大きさを決定した前記伸縮範囲が重なった場合には、前記第１探索部からの最大類似度に代えて前記第２探索部からの前記最大類似度を前記予測部で用いるように制御する更新部と、前記テンプレートの大きさが任意の範囲に至るまで、前記テンプレートを前記伸縮部によって拡大、又は、縮小し、前記第１探索部と前記第２探索部によって前記拡大、又は、縮小したテンプレートによって探索を繰り返す繰り返し部と、を有するテンプレート照合装置。
請求項3
前記限界値算出部、前記第１限界値算出部、又は、前記第２限界値算出部は、ｎ次元の前記テンプレートの全ての次元の長さが等倍率の前記伸縮率α（但し、α＞０である）で拡大、又は、縮小する場合に、前記限界値算出部、前記第１限界値算出部、又は、前記第２限界値算出部は、Ｓ（但し、０≦Ｓ≦１である）を前記照合部によって算出された前回の最大類似度、θ（但し、０≦θ≦１である）を前記閾値として、Ｓ／θ＜αｎ＜１／（１＋Ｓ−θ）・・・（Ａ）によって前記伸縮率αの前記上限値と前記下限値を算出する、請求項２記載のテンプレート照合装置。
請求項4
前記探索部、前記第１探索部、又は、前記第２探索部は、正規化ヒストグラム交差で前記類似度を算出する、請求項２記載のテンプレート照合装置。
請求項5
ｎ次元の前記テンプレートの全ての次元の長さが等倍率の前記伸縮率α（但し、α＞０である）で拡大、又は、縮小する場合において、前記探索部、前記第１探索部、又は、前記第２探索部は、Ｓ（但し、０≦Ｓ≦１である）を前記照合部によって前回の探索で算出された最大類似度、θ（０≦θ≦１）を前記閾値、ｈｗ、ｈｔを、それぞれ前記入力信号上の前記探索窓中の特徴量の分布と前記テンプレートの特徴量の分布であるヒストグラムを表すｍ次元のベクトル、ｈｗｉ、ｈｔｉをそれぞれ前記入力信号上の前記探索窓の特徴量と前記テンプレートの特徴量のｉ番目のヒストグラム要素を表すとすると、今回の最大類似度を下記の式Ｂによって示す関数Ｓ（・）で算出し、前記限界値算出部、前記第１限界値算出部、又は、前記第２限界値算出部は、下記の式Ｃで前記伸縮率αの前記上限値と前記下限値を算出し、但し、ｆ（θ）−１はｆ（α）＝θを満たすベクトルである前記伸縮率αを出力するものとする、請求項４記載のテンプレート照合装置。
請求項6
ｎ次元の前記テンプレートの各次元の長さが異なる前記伸縮率αｉ（但し、αｉ＞０であり、１＜ｉ＜ｎである）で拡大、又は、縮小する場合において、前記限界値算出部、前記第１限界値算出部、又は、前記第２限界値算出部は、下記の式Ｄで前記伸縮率αの前記上限値と前記下限値を算出し、請求項２記載のテンプレート照合装置。
請求項7
前記探索部、前記第１探索部、又は、前記第２探索部は、前記入力信号を複数の領域に分割し、前記探索を前記分割した領域毎に行う、請求項２記載のテンプレート照合装置。
請求項8
前記探索部、前記第１探索部、又は、前記第２探索部は、平均輝度値によるノルムにを用いて類似度を算出する、請求項２記載のテンプレート照合装置。
請求項9
入力信号が入力する入力ステップと、（１）予め決められた初期値の大きさのテンプレート、又は、前記初期値の大きさのテンプレートを任意の伸縮範囲内の伸縮率で順番に拡大、又は、縮小したテンプレートを前記入力信号上で探索位置を移動させながら類似度を求めるものであり、（２）前記各探索位置において、前記テンプレートの特徴量の分布と前記入力信号における探索窓内の特徴量の分布に基づく類似度を求め、（３）前記類似度の中の最大類似度を求める第１探索ステップと、前記最大類似度に基づいて前記テンプレートを拡大、又は、縮小したときの、前記入力信号に対する予測最大類似度を予測する予測ステップと、前記予測最大類似度から、前記テンプレートを拡大、又は、縮小したときの最大類似度が閾値を超えないように、前記テンプレートの前記伸縮率の上限値と下限値を算出する第１伸縮率算出ステップと、前記上限値と前記下限値から決まる伸縮範囲内の前記伸縮率によって前記テンプレートを伸縮する伸縮ステップと、（１）前記伸縮したテンプレートを前記入力信号上で探索位置を移動させながら類似度を求めるものであり、（２）前記各探索位置において、前記テンプレートの特徴量の分布と前記入力信号における探索窓内の特徴量の分布に基づく類似度を求め、（３）前記類似度の中の最大類似度を求める第２探索ステップと、前記最大類似度から、前記テンプレートを拡大、又は、縮小したときの最大類似度が前記閾値を超えないように、前記テンプレートの伸縮率の拡大上限値、又は、縮小下限値からなる伸縮範囲を算出する第２伸縮率算出ステップと、前記第２伸縮率算出ステップによって求められた前記伸縮範囲と、前記第１探索ステップで探索に用いられた前記テンプレートの大きさを決定した前記伸縮範囲が重なっていない場合には、前記伸縮ステップで用いられる前記伸縮率を変化させるバックトラックステップと、前記第２伸縮率算出ステップによって求められた前記伸縮範囲と、前記第１探索ステップで探索に用いられた前記テンプレートの大きさを決定した前記伸縮範囲が重なった場合には、前記第１探索ステップからの最大類似度に代えて前記第２探索ステップからの前記最大類似度を前記予測ステップで用いるように制御する更新ステップと、前記テンプレートの大きさが任意の範囲に至るまで、前記テンプレートを前記伸縮ステップによって拡大、又は、縮小し、前記第１探索ステップと前記第２探索ステップによって前記拡大、又は、縮小したテンプレートによって探索を繰り返す繰り返しステップと、を有するテンプレート照合方法。
請求項10
コンピュータに、入力信号が入力する入力機能と、（１）予め決められた初期値の大きさのテンプレート、又は、前記初期値の大きさのテンプレートを任意の伸縮範囲内の伸縮率で順番に拡大、又は、縮小したテンプレートを前記入力信号上で探索位置を移動させながら類似度を求めるものであり、（２）前記各探索位置において、前記テンプレートの特徴量の分布と前記入力信号における探索窓内の特徴量の分布に基づく類似度を求め、（３）前記類似度の中の最大類似度を求める第１探索機能と、前記最大類似度に基づいて前記テンプレートを拡大、又は、縮小したときの、前記入力信号に対する予測最大類似度を予測する予測機能と、前記予測最大類似度から、前記テンプレートを拡大、又は、縮小したときの最大類似度が閾値を超えないように、前記テンプレートの前記伸縮率の上限値と下限値を算出する第１伸縮率算出機能と、前記上限値と前記下限値から決まる伸縮範囲内の前記伸縮率によって前記テンプレートを伸縮する伸縮機能と、（１）前記伸縮したテンプレートを前記入力信号上で探索位置を移動させながら類似度を求めるものであり、（２）前記各探索位置において、前記テンプレートの特徴量の分布と前記入力信号における探索窓内の特徴量の分布に基づく類似度を求め、（３）前記類似度の中の最大類似度を求める第２探索機能と、前記最大類似度から、前記テンプレートを拡大、又は、縮小したときの最大類似度が前記閾値を超えないように、前記テンプレートの伸縮率の拡大上限値、又は、縮小下限値からなる伸縮範囲を算出する第２伸縮率算出機能と、前記第２伸縮率算出機能によって求められた前記伸縮範囲と、前記第１探索機能で探索に用いられた前記テンプレートの大きさを決定した前記伸縮範囲が重なっていない場合には、前記伸縮機能で用いられる前記伸縮率を変化させるバックトラック機能と、前記第２伸縮率算出機能によって求められた前記伸縮範囲と、前記第１探索機能で探索に用いられた前記テンプレートの大きさを決定した前記伸縮範囲が重なった場合には、前記第１探索機能からの最大類似度に代えて前記第２探索機能からの前記最大類似度を前記予測機能で用いるように制御する更新機能と、前記テンプレートの大きさが任意の範囲に至るまで、前記テンプレートを前記伸縮機能によって拡大、又は、縮小し、前記第１探索機能と前記第２探索機能によって前記拡大、又は、縮小したテンプレートによって探索を繰り返す繰り返し機能と、を実現させるためのテンプレート照合プログラム。